package cn.lena.sort;

/**
 * lena
 * t归并排序
 * 2021-03-04
 */
public class MergeSort {

	/*
	 * 归并排序（排序入口）
	 * a ==> 需要排序的数组
	 */
	public int[] mergeSort(int []nums){
		if (nums == null || nums.length == 0) {
			return new int[0];
		}
		return divide(nums, 0, nums.length - 1);
	}

	/*
	 * 将大的分成小的
	 * a ==> 需要排序的数组
	 */
	public int[] divide(int[] nums, int l, int r) {
		// 递归出口
		if (l >= r) {
			return nums;
		}
		int mid = (l + r) / 2;
		divide(nums, l, mid);
		divide(nums,mid + 1, r);
		merge(nums, l, mid, r);
		return nums;
	}

	/*
	 * 排序
	 * 归并部分：[l,mid]和[mid+1,r]
	 * a ==> 需要排序的数组
	 */
	public void merge(int[] nums, int l, int mid, int r) {
		int[] temp = new int[r - l + 1];	//新的空间用于存放已排好的序列
		int i = l;
		int j = mid + 1;
		int cur = 0;
		while (i <= mid && j <= r) {
			if (nums[i] < nums[j]) {
				temp[cur] = nums[i];
				i++;
			} else {
				temp[cur] = nums[j];
				j++;
			}
			cur++;
		}
		while (i <= mid) {
			temp[cur] = nums[i];
			i++;
			cur++;
		}
		while (j <= r) {
			temp[cur] = nums[j];
			j++;
			cur++;
		}
		// 将排好序的临时数组重新赋值给原数组，注意是下标从l-r
		for (int x = 0; x < temp.length; x++) {
			nums[l++] = temp[x];
		}
		//数组是引用类型，在函数内修改后会修改实际数据，因此不用返回也可以。
	}

}
